An official website of the United States government
Free, publicly-accessible full text available May 1, 2026
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
-
The spread of a graph $$G$$ is the difference between the largest and smallest eigenvalue of the adjacency matrix of $$G$$. In this paper, we consider the family of graphs which contain no $$K_{s,t}$$-minor. We show that for any $$t\geq s \geq 2$$ and sufficiently large $$n$$, there is an integer $$\xi_{t}$$ such that the extremal $$n$$-vertex $$K_{s,t}$$-minor-free graph attaining the maximum spread is the graph obtained by joining a graph $$L$$ on $(s-1)$ vertices to the disjoint union of $$\lfloor \frac{2n+\xi_{t}}{3t}\rfloor$$ copies of $$K_t$$ and $$n-s+1 - t\lfloor \frac{2n+\xi_t}{3t}\rfloor$$ isolated vertices. Furthermore, we give an explicit formula for $$\xi_{t}$$ and an explicit description for the graph $$L$$ for $$t \geq \frac32(s-3) +\frac{4}{s-1}$$.more » « lessFree, publicly-accessible full text available January 17, 2026
-
The spread of a graph $$G$$ is the difference between the largest and smallest eigenvalue of the adjacency matrix of $$G$$. Gotshall, O'Brien and Tait conjectured that for sufficiently large $$n$$, the $$n$$-vertex outerplanar graph with maximum spread is the graph obtained by joining a vertex to a path on $n-1$ vertices. In this paper, we disprove this conjecture by showing that the extremal graph is the graph obtained by joining a vertex to a path on $$\lceil(2n-1)/3\rceil$$ vertices and $$\lfloor(n-2)/3\rfloor$$ isolated vertices. For planar graphs, we show that the extremal $$n$$-vertex planar graph attaining the maximum spread is the graph obtained by joining two nonadjacent vertices to a path on $$\lceil(2n-2)/3\rceil$$ vertices and $$\lfloor(n-4)/3\rfloor$$ isolated vertices.more » « less
-
In this paper, we prove an Azuma-Hoeffding-type inequality in several classical models of random configurations by a Ricci curvature approach. Adapting Ollivier’s work on the Ricci curvature of Markov chains on metric spaces, we prove a cleaner form of the corresponding concentration inequality in graphs. Namely, we show that for any Lipschitz function f on any graph (equipped with an ergodic random walk and thus an invariant distribution ν) with Ricci curvature at least κ > 0, we have ν (|f − Eνf| ≥ t) ≤ 2 exp(−t^2κ/7).more » « less
